// scalaxx - Scala XML eXtensions
// (c) 2009, Normen Müller, normen.mueller@gmail.com
// $Id: Differ.scala 48 2009-11-12 11:29:56Z normen.mueller $
package scalaxx.diff

import java.io.File

import scala.xml.{NodeSeq, NodeBuffer, Node, Text, MetaData, Null}
import scala.xml.XML.{loadFile}
import scala.xml.Utility.{trimProper}

import scaup.eq.Slit
import scaup.eq.EquivalenceSystem

import scalaxx.Views._
import scalaxx.path._

/** XML Differencing algorithms
 * 
 * @author <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 * @version 0.0.1 */
object Differ {
  type E[T] = EquivalenceSystem[T]
  
  def diff(src: File, tgt: File): List[Command] = diff(new E[NodeSeq] {},src,tgt)
  
  def diff[T >: Node](model: E[T], src: File, tgt: File): List[Command] = diff(model, loadFile(src), loadFile(tgt))
  
  def diff(src: NodeSeq, tgt: NodeSeq): List[Command] = diff(new E[NodeSeq] {}, src, tgt)
  
  def diff[T >: Node](model: E[T], src: NodeSeq, tgt: NodeSeq) = new Differ(model).diff(new NodeBuffer &+ (src map trimProper), new NodeBuffer &+ (tgt map trimProper))
}

/** XML Differ based on a equivalence model.
 * 
 * @thanks Serge Autexier and Marc Wager for their initial discussions on the general differencing algorithm.
 * @author <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 * @version 0.0.1 */
private [diff] class Differ(model: EquivalenceSystem[Node]) {
  import model._
  import scala.xml.NodeSeq._
  
  def diff(src: NodeSeq, tgt: NodeSeq): List[Command] = diff(src, tgt, Root.childAt(1),Nil).reverse
  
  private def diff(src: NodeSeq, tgt: NodeSeq, path: LocationPath, cs: List[Command]): List[Command] = (src,tgt) match {
    case (Empty, Empty)                                             => cs
    case (Empty, Seq(ht@Text(_), tt@_*))                            => diff(Empty, tgt.drop(1), path, append(path--, elem(ht)) :: cs)
    case (Empty, Seq(ht, tt@_*))                                    => diff(Empty, tt, path, append(path, elem(ht)) :: cs)
    case (Seq(hs@Text(_), ts@_*), Empty)                            => diff(ts, Empty, path++, remove(path.parent.text, elem(hs)) :: cs)
    case (Seq(hs, ts@_*), Empty)                                    => diff(ts, Empty, path++, remove(path, elem(hs)) :: cs)
    case (Seq(hs@Text(l), ts@_*), Seq(ht@Text(r), tt@_*)) if l == r => cs
    case (Seq(hs@Text(_), ts@_*), Seq(ht@Text(_), tt@_*))           =>
      diff(ts, tt, if(ts isEmpty) path-- else path++, append(path.parent, elem(ht)) :: remove(path.parent.text, elem(hs)) :: cs)
    case (Seq(hs, ts@_*), Seq(ht, tt@_*))                           => ((slit: Slit[Node]) =>
      diff(ts, slit.after, if(ts isEmpty) path-- else path++, slit.focus match {
        case Some(f) => diff(hs.child, f.child, if(hs.child isEmpty) path else path.childAt(1),
                             diff(hs.attributes, f.attributes, path) ::: (slit.before match { case Some(es) => List(before(path, (es map elem):_*)) case _ => Nil }) ::: cs)
        case _       => (slit.before match { case Some(es) => List(before(path, (es map elem):_*)) case _ => Nil }) ::: List(remove(path, elem(hs))) ::: cs
                           
      })
    )(findEquivTo(tgt, hs))
  }
  
  private def diff(src: MetaData, tgt: MetaData, xpath: path.LocationPath) =
    (for(a: MetaData <- tgt if(! (a containedIn src))) yield
     append(xpath.attributes, attr(a.copy(Null)))).toList :::    
      (for(a: MetaData <- src if(! (a containedIn tgt))) yield
       remove(xpath.attributeAt(src.positionOf(a)), attr(a.copy(Null)))).toList
}
